package 回溯.排列;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/7/21 17:16
 */
public class lc31下一个排列 {


    /*
     没啥可说的, 会就是会
     不会就是不会!

     // 说实话就是,背
     记住这个题 是怎么做的
     */

    public void solution(int nums[]) {
        int i;
        boolean flag = false;
        for (i = nums.length - 1; i > 0; i--) {
            if (nums[i] > nums[i - 1]) {
                flag = true;
                break;
            }
        }
        // not found  the position
        if (!flag) {
            for (int l = 0, r = nums.length - 1; l < r; l++, r--) {
                int temp = nums[l];
                nums[l] = nums[r];
                nums[r] = temp;
            }
            return;
        }
        // found
        for (int j = nums.length - 1; j >= i; j--) {
            if (nums[i - 1] < nums[j]) {
                int temp = nums[j];
                nums[j] = nums[i - 1];
                nums[i - 1] = temp;
                break;
            }
        }
        for(int l = i, r = nums.length - 1;l < r;l++, r--){
            int temp = nums[r];
            nums[r] = nums[l];
            nums[l] = temp;
        }
    }

    @Test
    public void test(){
        int nums[] = {5,4,7,5,3,2};
        solution(nums);
    }


    /*
     从后向前遍历, 找到 能交换的两个数
     显然这种方式是错的

     - 果然这题没有这么简单
     */
    // 155/266
    public void solve(int nums[]) {
        boolean flag = false;
        for (int i = nums.length - 1; i > 0; i--) {
            if (nums[i] > nums[i - 1]) {
                int temp = nums[i];
                nums[i] = nums[i - 1];
                nums[i - 1] = temp;
                flag = true;
                break;
            }
        }
        if (!flag) { // 说明找不到, 直接 把数组翻转一下就 可以了
            for (int l = 0, r = nums.length - 1; l < r; l++, r--) {
                int temp = nums[l];
                nums[l] = nums[r];
                nums[r] = temp;
            }
        }
    }
}
